//原文链接
//@https://blog.csdn.net/ITSOK_123/article/details/124611336
//递归实现（O(n),O(n)）
TreeNode* invertTree(TreeNode* root) {
        if(root == nullptr) return root;
        TreeNode *temp = root->right;
        //左右互换
        root->right = invertTree(root->left);
        root->left = invertTree(temp);
        return root;
    }

//前序迭代（O(n),O(n)）
TreeNode* invertTree(TreeNode* root) {
        // 通过前序遍历进行树的反转
        if (root == NULL) return root;
        stack<TreeNode*> st;
        TreeNode *node = root;
        // 栈不为空或者当前节点不为空就继续
        while(!st.empty() || node){
            // 节点下沉
            while(node){
                st.push(node);
                // 节点交换
                swap(node->left,node->right);
                node = node->left;
            }
            // 访问右子树
            TreeNode *cur = st.top();
            st.pop();
            node = cur->right;
        }
        return root;
    }

//层次迭代（O(n),O(n)）
TreeNode* invertTree(TreeNode* root) {
        // 通过层次遍历进行树的反转
        if (root == NULL) return root;
        queue<TreeNode*> que;
        TreeNode *node = root;
        que.push(root);
        // 队列不空继续处理
        while(!que.empty()){
            size_t _size = que.size();
            while(_size--){
                TreeNode* cur = que.front();
                que.pop();
                // 交换左右子树
                swap(cur->left,cur->right);
                if(cur->left !=nullptr) que.push(cur->left);
                if(cur->right !=nullptr) que.push(cur->right);
            }
        }
        return root;
    }


